/*
 * @lc app=leetcode id=210 lang=cpp
 *
 * [210] Course Schedule II
 */
class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> result;
        if (numCourses < 1 || prerequisites.size() < 1) {
            for (int i=0; i<numCourses;i++){
                result.push_back(i);
            }
            return result;
        }

        vector<vector<int>> graph(numCourses);
        buildGraph(prerequisites, graph);
        vector<int> queue;

        int node;
        map<int, bool> visited;
        map<int, bool> done;

        for (int node=0; node<graph.size(); node++) {
            if (!done[node] && !hasCycle(graph, done, visited, queue, node)) {
                return {};
            }
        }
        reverse(queue.begin(), queue.end());

        return queue;
    }

    bool hasCycle(vector<vector<int>>& graph, map<int, bool>& done, map<int, bool>& visited, vector<int>& queue, int node) {
        if (visited[node]) {
            return false;
        }
        
        if (done[node]) {
            return true;
        }

        visited[node] = true;
        done[node] = true;
        for (auto n:graph[node]) {
            if (!hasCycle(graph, done, visited, queue, n)) {
                return false;
            }
        }
        queue.push_back(node);
        visited[node] = false;
        return true;
    }

    void buildGraph(vector<vector<int>>& prerequisites, vector<vector<int>>& graph ) {
        int from, to;
        for (vector<int> it : prerequisites) {
            from = it[0];
            to = it[1];
            graph[to].push_back(from);
        }
    }
};

